package algorithm_demo.demo01;

/**
 * 两数相加
 * 给你两个非空 的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 * 你可以假设除了数字 0 之外，这两个数都不会以 0开头。
 * <p>
 * 输入：l1 = [2,4,3], l2 = [5,6,4]
 * 输出：[7,0,8]
 * 解释：342 + 465 = 807.
 * <p>
 * 输入：l1 = [0], l2 = [0]
 * 输出：[0]
 * <p>
 * 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
 * 输出：[8,9,9,9,0,0,0,1]
 * <p>
 * <p>
 * 链接：https://leetcode.cn/problems/add-two-numbers
 *
 * @author Api
 * @date 2023/1/29 0:14
 */
public class Code19_AddTwoNumbers {
    public static class ListNode {
        public int val;//值传递
        public ListNode next;//对象，引用传递

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args){
        ListNode head1 = new ListNode(2, new ListNode(4, new ListNode(3, new ListNode(5))));
        ListNode head2 = new ListNode(5, new ListNode(6, new ListNode(4)));
        ListNode listNode = addTwoNumbers(head1, head2);
        System.out.println(listNode);
    }
    /*
        这里需要注意的是Java中基本类型是值传递，对象为引用类型
        值传递（pass by value）是指在调用方法时将实参复制一份传递到方法中，这样当方法对形参进行修改时不会影响到实参。
        引用传递（pass by reference）是指在调用方法时将实参的地址直接传递到方法中，那么在方法中对形参所进行的修改，将影响到实参。
    */
    //三个阶段：
    //1. 长链表有，短链表也有
    //2. 长链表有，短链表无
    //3. 长链表无，短链表无
    public static ListNode addTwoNumbers(ListNode head1, ListNode head2) {
        int len1 = getLinkedListLength(head1);
        int len2 = getLinkedListLength(head2);
        //较长的链表是谁
        ListNode l = len1 >= len2 ? head1 : head2;
        ListNode s = l == head1 ? head2 : head1;
        //l表示的为长链表，s表示的是短链表
        ListNode curL = l;
        ListNode curS = s;
        ListNode last = curL;
        int carry = 0;
        int curNum = 0;
        //优先短的链表s先循环
        while (curS != null) {
            //当前节点加和
            curNum = curL.val + curS.val + carry;
            //求模可得当前节点的value值
            curL.val = curNum % 10;
            //需要进位的标识，商为几，则进几位；
            carry = curNum / 10;
            last = curL;//记录长链表最后一个Node节点
            curL = curL.next;
            curS = curS.next;
        }
        //当短链表s执行完后，需要将剩余的长链表l和进位标识求和，做取模和求商，判断是否需要进位
        while (curL != null) {
            curNum = curL.val + carry;
            curL.val = curNum % 10;
            carry = curNum / 10;
            last = curL;
            curL = curL.next;
        }
        if (carry != 0) {
            last.next = new ListNode(1);
        }
        return l;
    }


    //获取链表的长度
    public static int getLinkedListLength(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }
}
